import java.util.HashMap;

/**
* @description: 1027. 最长等差数列
* @author hewei
* @date 2022/10/11 16:31
* @version 1.0
*/

public class LongestArithSeqLength {

    public int longestArithSeqLength1(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = nums[i] - nums[j];
                dp[i].put(temp, Math.max(dp[j].getOrDefault(temp, 1) + 1, dp[i].getOrDefault(temp, 0)));
                ans = Math.max(ans, dp[i].get(temp));
            }
        }
        return ans;
    }

    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][1001];
        int ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int delta = nums[i] - nums[j];
                if (delta < 0) delta = -delta + 500;
                dp[i][delta] = Math.max(dp[j][delta] + 1, dp[i][delta]);
                ans = Math.max(ans, dp[i][delta]);
            }
        }
        return ans + 1;
    }
}